package com.xyzwps.example.data;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Trie {

    private final Node root;

    public Trie() {
        this.root = new Node((char) 0, false);
    }


    /**
     * This method would
     * <ul>
     *  <li>ignore null and empty list</li>
     *  <li>throw an exception when list has a null element</li>
     * </ul>
     */
    public Trie add(CharSequence ts) {
        if (ts == null || ts.isEmpty()) {
            return this;
        }

        var current = this.root;
        final int len = ts.length();
        for (int i = 0; i < len; i++) {
            var t = ts.charAt(i);
            var c = current.children;
            if (!c.containsKey(t)) {
                c.put(t, new Node(t, false));
            }
            current = c.get(t);
        }
        current.end = true;

        return this;
    }

    /**
     * This method would ignore null and empty array.
     */
    public Trie add(char[] ts) {
        if (ts == null || ts.length == 0) {
            return this;
        }

        var current = this.root;
        for (var t : ts) {
            var c = current.children;
            if (!c.containsKey(t)) {
                c.put(t, new Node(t, false));
            }
            current = c.get(t);
        }
        current.end = true;

        return this;
    }

    public List<Integer> match(CharSequence cs) {
        return this.match(cs, 0);
    }

    public List<Integer> match(CharSequence cs, int start) {
        List<Integer> result = new ArrayList<>();
        final int len = cs.length();
        var current = this.root;
        for (int i = start; i < len; i++) {
            var c = cs.charAt(i);
            if (current.children.containsKey(c)) {
                var matchedNode = current.children.get(c);
                if (matchedNode.end) {
                    result.add(i + 1);
                }
                current = matchedNode;
            } else {
                break;
            }
        }
        return result;
    }

    @Override
    public String toString() {
        return root.toString();
    }


    private static class Node {
        final char value;
        final Map<Character, Node> children;
        boolean end;

        Node(char value, boolean end) {
            this.value = value;
            this.children = new HashMap<>();
            this.end = end;
        }

        @Override
        public String toString() {
            var sb = new StringBuilder();
            this.buildString(0, true, sb);
            return sb.toString();
        }

        private void buildString(int level, boolean last, StringBuilder sb) {
            sb.append(" ┆ ".repeat(level));
            sb.append(last ? " ┗━" : " ┣━");
//            sb.append(this.children.isEmpty() ? "━" : "━");
            sb.append(" ").append(this.value == 0 ? "☀" : this.value);
            if (end) sb.append(" <-------");
            sb.append("\n");

            var keys = this.children.keySet();
            int i = 1;
            for (var key : keys) {
                this.children.get(key).buildString(level + 1, i == keys.size(), sb);
                i++;
            }
        }
    }

}
